/*
剑指 Offer 10- I. 斐波那契数列
解题思路：滚动数组思想，三个变量，前两个变量决定第三个变量。
 */
public class Offer10 {
  public static void main(String[] args) {
    System.out.println(new Offer10().fib(4));
  }

  public int fib(int n) {
    if (n < 2) {
      return n;
    }
    int p = -1, q = 0, r = 1;
    for (int i = 2; i <= n; ++i) {
      p = q;
      q = r;
      r = (p + q) % 1000000007;
    }
    return r;
  }
}
